package com.ys.p4Queue队列;

import com.sun.jmx.snmp.SnmpNull;

/**
 * 描述: 使用单链表模拟实现"队列"
 * --这样的队列不是有限资源的竞争关系,只是一种无限下去的操作单链表
 * FIFO 先进先出
 * 核心:队列的出口在"链表尾部",队列的出口在"链表的头部"
 *  使用链表模拟队列的实现:
 *  1: 单链表特点: 有首尾节点,有指向,尾节点指向为null
 * @author CodeYang
 * @version 2021/1/3 21:32
 */
public class LinkedListQueue<E> implements Queue<E>{
    /**
     * 头节点
     */
    private QueueNode<E> fontNode;
    /**
     * 尾节点
     */
    private QueueNode<E> rearNode;
    /**
     * 用于保存实际添加元素的个数
     */
    private int size;


    private static class QueueNode<E> {
        /**
         * 用于保存节点数据
         */
        private E item;
        /**
         * 保存指向下一个节点的指针
         */
        private QueueNode<E> next;

        /**
         * 专门实现item的初始化
         * @param item
         */
        public QueueNode(E item) {
            this.item = item;
        }
    }

    /**
     * 在队尾添加元素
     * 开始队首与队尾都是一体的,但是无论怎么添加根据单链表的模拟实现:
     * 添加的元素自动添加在尾节点,并更新尾节点
     * @param element
     * @return
     */
    @Override
    public boolean offer(E element) {
        //1 封装数据为节点
        QueueNode<E> node = new QueueNode<>(element);
        //2 把node 添加进入"队列"链表
        //2-1 处理元素为空情况;
        if (isEmpty()){
            // 如果为空怎么,此时链表|队列未初始化,把队列初始化,队首与队尾都是node
            fontNode = rearNode = node;
        } else {
            //2-2 不为空 把node插入到队列|链表末尾,在更新队尾
            // 添加节点到队尾
            rearNode.next = node;
            //更新队尾
            rearNode = node;
        }
        // 添加成功执行元素添加
        size++;
        // 如果执行添加操作成功,队首指向的下一个节点必定不为空
        return fontNode.next != null;
    }

    /**
     * 获得队首的元素，不会执行出队操作
     * 查看队首元素
     *
     * @return 判断队列是否为空 空返回null,不为空返回队首节点的 数据
     */
    @Override
    public E peek() {
        // 判断队列是否为空 空返回null,不为空返回队首节点的 数据
        return isEmpty() ? null : fontNode.item;
    }

    /**
     * 获得队首的元素，并且队首元素出队
     *
     * @return 判断队列是否为空 空返回null,不为空返回队首节点的 数据
     */
    @Override
    public E poll() {
        if (isEmpty()){
            return null;
        }
        // 出队操作, FIFO 先进先出 就是把 队首概念节点 先后移动一个节点
        // 先保存"原队首"的数据
        E oldValue = fontNode.item;
        // 更新关系-> 获得队首后一个节点-->取消next指向--->在更新队首
        QueueNode<E> nextNode = fontNode.next;
        // 取消原队首的链表指向 GC回收 当前指向值
        fontNode.next = null;
        // 更新队首
        fontNode = nextNode;
        // 出队,size--
        size--;
        //返回原队首数据
        return oldValue;
    }

    /**
     * 判断队列是否为空。
     *
     * @return 如果队列为空，则返回true；如果队列不为空，则返回false。
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
}
